package LeetCode;

public class LC_287 {
    public static int findDuplicate(int[] nums) {
        //不修改数组 nums 且只用常量级 O(1) 的额外空间
        //不修改原数组，O(n)额外空间
        int n = nums.length;
        int[] save = new int[n+1];
        for (int i:nums
        ) {
            if (save[i]!= i){
                save[i] = i;
            }else{
                return i;
            }

        }
        return 0;

    }

    public static void main(String[] args) {
        System.out.println(findDuplicate(new int[]{1,3,4,2,2}));
    }
}
